/*
 * Rutas.h
 *
 *  Created on: 14-dic-2008
 *      Author: burce
 */

#ifndef RUTAS_H_
#define RUTAS_H_

#include <iostream>
#include <LEDA/graph/ugraph.h>
#include <LEDA/core/string.h>
#include <LEDA/graph/node_array.h>
#include <LEDA/core/list.h>
#include <LEDA/graph/graph_alg.h>
#include <LEDA/graph/node_matrix.h>
#include <LEDA/graphics/graphwin.h>

using namespace leda;
using namespace std;

typedef node_matrix<int> matriz;
typedef GRAPH<int, int> grafo;

class Rutas {
private:
	//Variables para el TSP
	node_array<bool> filActiva, colActiva;
	node_array<node> suc, pred;
	list<edge> tour;     //Almacena soluciones parciales
	list<edge> solucion; //Almacena soluciones finales
	node_map2<edge> M;
	int costoMin;


	void pintarTSP(GraphWin& GW);

public:
	static const int INF = 1000000;
	Rutas();

	bool fleury(GRAPH <int, int>& G, GraphWin& GW);
	bool floyd(GRAPH <int, int>& G, node_matrix <edge>& P, node_matrix <int>& W);
	bool carteroChinoSimetrico(GRAPH <int, int>& G, GraphWin& GW);
	bool carteroChinoAsimetrico(GRAPH <int, int>& G, GraphWin& GW);
	bool carteroChino(GRAPH <int, int>& G, GraphWin& GW);
	virtual ~Rutas();

	void tspAsimetrico(GraphWin& GW);
	void tsp(int aristas, int costo, matriz A, grafo& G);
};

#endif /* RUTAS_H_ */
